Welcome to Lecture 2. Having established the overall objectives for this course, we now dive into the fundamental Data Structures that form the building blocks of algorithm design: Arrays and Linked Lists.
Arrays and Linked Lists are the most basic and critical ways we organize data in memory, representing the core conflict between contiguous and dispersed storage management.
Definition: A Data Structure is a specialized format for organizing and storing data to facilitate efficient access and modification.
- Arrays store elements in contiguous memory locations, allowing for direct calculation of element addresses.
- Linked Lists store elements in dispersed memory locations, connected only by explicit pointers.
- Array access is Direct Indexing ($O(1)$), while Linked List access requires Traversal ($O(n)$).
- Insertion/Deletion in an Array requires shifting elements, resulting in $O(n)$ complexity.
- Insertion/Deletion in a Linked List only requires Pointer Relinking, achieving $O(1)$ if the position $i$ is known.
- Linked Lists incur higher Space Overhead because each node must store data plus a `next` pointer.
Complexity Comparison
| Feature | Array | Singly Linked List |
|---|---|---|
| Memory Allocation | Contiguous (Fixed Block Size $n$) | Dispersed (Dynamic Pointers) |
| Access Time | $O(1)$ | $O(n)$ |
| Insertion/Deletion | $O(n)$ | $O(1)$ (if position $i$ is known) |
| Space Overhead | Minimal (data only) | High (data + next pointer) |